package leetcode_day._2021._202104._2131;

import general_class.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/25 8:29
 * 递增顺序搜索树
 * 使用中序遍历，然后把值赋给新定义的根节点
 */
public class _25_897 {

    public TreeNode increasingBST(TreeNode root) {
        if (null == root) return root;
        TreeNode ans = new TreeNode();
        List<Integer> tmp = new ArrayList<>();
        iot(root, tmp);
        TreeNode cur = ans;
        for (int i = 0; i < tmp.size(); i++) {
            cur.val = tmp.get(i);
            if (i != tmp.size() - 1) {
                cur.right = new TreeNode();
                cur = cur.right;
            }
        }
        return ans;
    }

    public void iot(TreeNode root, List<Integer> tmp) {
        if (null == root.left && null == root.right) {
            tmp.add(root.val);
            return;
        }
        if (null != root.left) iot(root.left, tmp);
        tmp.add(root.val);
        if (null != root.right) iot(root.right, tmp);
    }
}
